/*
 * nodeBroker.cpp
 *
 *  Created on: Sep 18, 2011
 *      Author: Edward
 */



#include "puzzleSettings.h"
#include <exception>
#include "node.cpp"

class nodeBroker{
	node *freeNodeList;  //list of nodes not currently being used on tree.
	node *allocNodeList; //list of nodes currently on tree.
	node * initNodes;  //occupy memory for initial set of nodes.


public:
	unsigned int newNodeCalls;
	unsigned int memUsed;
	unsigned int nodesRecycled;

	/*
	 * Constructor -- places all the initial nodes on the free list;
	 * Initializes both allocated and free lists.
	 *
	 * TODO: OPTIMIZATION POSSIBILIY ---  use a counter to track how many initial nodes have been allocated
	 * Avoids placing all nodes on free list, removing startup cost.
	 */
	nodeBroker(){
		allocNodeList = NULL; //lists start out empty.
		freeNodeList = NULL;
		newNodeCalls=0;
		memUsed = 0;
		nodesRecycled = 0;

		initNodes = new node[memSize];
	}

	~nodeBroker(){
		//first deal with removing anything from list which was not dynamically allocated.
		for(unsigned int i = 0; i < memSize; i++){
			//check to make sure not head of either list
			node* remove = &initNodes[i];
			if(remove == allocNodeList){
				allocNodeList = allocNodeList->next;
				if(allocNodeList != NULL)
					allocNodeList->prev = NULL;
			} else if (remove == freeNodeList){
				freeNodeList = freeNodeList->next;
				if(freeNodeList !=NULL)
					freeNodeList->prev = NULL;
			}
			//node is not head of either list now.
			if(remove->prev != NULL)
				remove->prev->next = remove->next;
			if(remove->next != NULL)
				remove->next->prev = remove->prev;
			//node is now cut out of the list it was in.
		}
		//we do not need to delete initNodes since they were not dynamically allocated.

		//Now we need to free every node we created after init set.
		while(allocNodeList != NULL){
			node * remove = allocNodeList;
			allocNodeList = allocNodeList->next;
			delete remove;
		}
		while(freeNodeList != NULL){
			node * remove = freeNodeList;
			freeNodeList = freeNodeList->next;
			delete remove;
		}
		//ASSERT: all lists are null, and all memory allocated has been freed.
		delete initNodes;
	}


	/*
	 * RESET()
	 *
	 * resets the broker, putting all nodes on the free list.
	 */
	void reset(){
		while(allocNodeList != NULL){
			node * temp = allocNodeList; // head element on allocated list.
			allocNodeList = allocNodeList -> next; //advance head of allocated list;
			temp -> next = freeNodeList;
			if(freeNodeList != NULL)
				freeNodeList->prev = temp; //if FreeNodeList was not empty, set prev to new head
			freeNodeList = temp; //new head of free list;
		}
		newNodeCalls = 0; // resetting stats on nodeBroker.
	}

	//Every new board needs to be initialized with
	//a parent.
	//a board setting.
	//a cost value.
	node* newNode(){
		if(memUsed >= maxMemSize)
			return NULL; //out of memory


		//return new node();  /// FOR TESTING WITHOUT A NODE BROKER
		node * temp;
		if(stats)
			newNodeCalls++;
		if(freeNodeList == NULL){
			// Need to allocate memory for new node;

			if(memUsed < memSize){//Check if used all preallocated memory
				temp = &initNodes[memUsed];
				memUsed ++;
			} else { //we have run out of preallocated memory
				if(stats)
					memUsed++;
				try {
					temp = new node();
				} catch(exception &e) {
					cout << "Ran Out Of Memory, Taking Best Solution" << endl;
					return NULL;
				}
			}
			// insert node at head of allocated list;

			temp->next = allocNodeList;
			if(temp->next != NULL)
				temp->next->prev = temp;
			temp->prev = NULL;
			allocNodeList = temp;
		} else {
			//get hold of next free node
			temp = freeNodeList;
			//cut node out of free list
			freeNodeList = freeNodeList->next;
			if(freeNodeList != NULL)
				freeNodeList->prev = NULL;
			//insert node into allocated list
			temp->next = allocNodeList;
			// temp->prev = NULL;  // this should be redundant because it is head of list and should be null!!
			if(temp->next != NULL)
				temp->next->prev = temp; //
			allocNodeList = temp;  //temp is the new head of the list.
		}
		//reaching here assumes temp is assigned space.
		return temp;
	}

	//RECYCLE NODE,
	//ASSERT: These nodes are no longer used in search.
	//Put node on the freeNodeList to be allocated if new nodes needed.
	void recycle(node * rec){
		///delete rec;  /// for testing without a node broker.

		nodesRecycled ++;

		if(rec->parent != NULL){ //if parent exists and parent has no more children referencing it, recycle parent.  set references to 0;
			if(rec->parent->references > 0)
				rec->parent->references--;
			if(rec->parent->references == 0){
				recycle(rec->parent);
			}
			rec->references = 0;
		}

		//ASSUMES NODE IS ALLOCATED
		if(rec == allocNodeList){
			//at head of allocated list, move list head over;
			allocNodeList = allocNodeList->next;
			allocNodeList->prev = NULL;
		} else {
			//rec has previous, but may not have next, cut out of list
			rec->prev->next = rec->next;
			if(rec->next != NULL)
				rec->next->prev = rec->prev;
			//rec is now out of allocated list
			rec->prev = NULL;
		}

		//add node to head of free list
		//ASSERT: rec prev is null;
		rec->next = freeNodeList;
		if(freeNodeList != NULL)
			rec->next->prev = rec;
		freeNodeList = rec;

		//ASSERT: rec is now head of freeNodeList and not on allocNodeList
	}
};
